package com.hy.str;

public class ReserveWords {

    /**
     * 151.翻转字符串里的单词
     * 力扣题目链接
     *
     * 给定一个字符串，逐个翻转字符串中的每个单词。
     *
     * 示例 1：
     * 输入: "the sky is blue"
     * 输出: "blue is sky the"
     *
     * 思路
     * 这道题目可以说是综合考察了字符串的多种操作。
     *
     * 一些同学会使用split库函数，分隔单词，然后定义一个新的string字符串，最后再把单词倒序相加，那么这道题题目就是一道水题了，失去了它的意义。
     *
     * 所以这里我还是提高一下本题的难度：不要使用辅助空间，空间复杂度要求为O(1)。
     *
     * 不能使用辅助空间之后，那么只能在原字符串上下功夫了。
     *
     * 想一下，我们将整个字符串都反转过来，那么单词的顺序指定是倒序了，只不过单词本身也倒序了，那么再把单词反转一下，单词不就正过来了。
     *
     * 所以解题思路如下：
     *
     * 移除多余空格
     * 将整个字符串反转
     * 将每个单词反转
     * 举个例子，源字符串为："the sky is blue "
     *
     * 移除多余空格 : "the sky is blue"
     * 字符串反转："eulb si yks eht"
     * 单词反转："blue is sky the"
     *
     * @return
     */
    /**
     * 思路：
     *	①反转字符串  "the sky is blue " => " eulb si yks eht"
     *	②遍历 " eulb si yks eht"，每次先对某个单词进行反转再移位
     *	   这里以第一个单词进行为演示：" eulb si yks eht" ==反转=> " blue si yks eht" ==移位=> "blue si yks eht"
     */
    public static String reserveWords(String s,int left,int right){
        char[] ch = s.toCharArray();
        String reserve = reserve(ch, 0, ch.length - 1);

        int k = 0;
        for (int i = 0; i < ch.length; i++) {
            if (ch[i]  ==' '){
                continue;
            }
            int tempCur = i;
            while (i < ch.length && ch[i] != ' '){
                i++;
            }
            // 遍历每一个 单词  然后进行反转
            for (int j = tempCur;j < i; j++){
                //步骤二：二次反转
                if (j == tempCur){
                    //对指定范围字符串进行反转，不反转从后往前遍历一个个填充有问题
                    reserve(ch,tempCur,i-1);
                }
                // //步骤三：移动操作
                ch[k++] = ch[j];
                if (j == i -1){
                    //避免越界情况，例如=> "asdasd df f"，不加判断最后就会数组越界
                    if (k < ch.length){
                        ch[k++] = ' ';
                    }
                }
            }
        }
//        System.out.println("==="+new String(ch));

        if (k == 0) {
            return "";
        } else {
            //参数三：以防出现如"asdasd df f"=>"f df asdasd"正好凑满不需要省略空格情况
            return new String(ch, 0, (k == ch.length) && (ch[k - 1] != ' ') ? k : k - 1);
        }
    }


    //  双指针法   反转字符串
    public static String reserve(char[] ch,int left,int right){
        // 位运算
        while (left < right){
            ch[left] ^= ch[right];
            ch[right] ^= ch[left];
            ch[left] ^= ch[right];

            left++;
            right--;
        }
        return new String(ch);
    }


    public static void main(String[] args) {
        String str = "asdasd df f";
        System.out.println("res: "+ reserveWords(str,0,str.length()));
    }
}
